package com.zm.demo.core.sort;

import java.util.Arrays;
import java.util.Random;

import static java.lang.System.out;

/**
 * @author zoum
 * @create 2020/3/10 13:17
 */
public class QuickSort2 {

    private static Random random = new Random();

    public static void main(String[] args){
        int[]a = {3,30,34,5,9,99,998,978,922,920,92,97,98543,98};
//        int[]a = {978,92};
        quickSort(a, 0, a.length-1);
        out.println(Arrays.toString(a));
    }

    public static void quickSort(int[]a, int start, int end) {
        if (start>=end){
            return;
        }
        int p = partition(a, start, end);

        quickSort(a, start,p-1);
        quickSort(a, p+1, end);
    }

    /**
     * 3,5,4,1,2  p=0
     * 3,5,4,1,2  p=0
     * 3,5,4,1,2  p=0
     * 1,3,5,4,2  p=1
     * 1,2,3,5,4  p=2
     * 借鉴插入排序的思想
     */
    private static int partition(int[] a, int start, int end) {
        int p = start;
        for (int i = start+1; i <= end ; i++) {
            if (!cmp(a[i], a[p])){
                int tmp = a[i];
                for (int j = i; j > p; j--) {
                    a[j] = a[j-1];
                }
                a[p] = tmp;
                p++;
            }
        }
        return p;

    }

    private static boolean cmp(int before, int after){
        String normal = String.valueOf(before) + after;
        String converse = String.valueOf(after) + before;

        for (int k = 0; k < normal.length() ; k++) {
            if (normal.charAt(k) > converse.charAt(k)){
                return true;
            }else if (normal.charAt(k) < converse.charAt(k)){
                return false;
            }
        }
        return false;
    }

    private static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}
